This is an interactive problem.
You have a sorted array of unique elements and an unknown size. You do not have an access to the array but you can use the ArrayReader interface to access it. You can call ArrayReader.get(i) that:
- returns the value at the
ithindex (0-indexed) of the secret array (i.e.,secret[i]), or - returns
231 - 1if theiis out of the boundary of the array.
You are also given an integer target.
Return the index k of the hidden array where secret[k] == target or return -1 otherwise.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: secret = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in secret and its index is 4.
Example 2:
Input: secret = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in secret so return -1.
Constraints:
1 <= secret.length <= 104-104 <= secret[i], target <= 104secretis sorted in a strictly increasing order.
Average Rating: 4.84 (45 votes)
Solution
Approach 1: Binary Search
Split into Two Subproblems
The array is sorted, i.e. one could try to fit into a logarithmic time complexity. That means two subproblems, and both should be done in a logarithmic time:
-
Define search limits, i.e. left and right boundaries for the search.
-
Perform binary search in the defined boundaries.
Define Search Boundaries
This is a key subproblem here.
The idea is quite simple. Let's take two first indexes, 0 and 1, as left and right boundaries. If the target value is not among these zeroth and the first element, then it's outside the boundaries, on the right.
That means that the left boundary could moved to the right,
and the right boundary should be extended. To keep logarithmic time
complexity, let's extend it twice as far: right = right * 2.
If the target now is less than the right element, we're done, the boundaries are set. If not, repeat these two steps till the boundaries are established:
-
Move the left boundary to the right:
left = right. -
Extend the right boundary:
right = right * 2.
Binary Search
Binary search is a textbook algorithm with a logarithmic time complexity. It's based on the idea to compare the target value to the middle element of the array.
-
If the target value is equal to the middle element - we're done.
-
If the target value is smaller - continue to search on the left.
-
If the target value is larger - continue to search on the right.
Prerequisites: left and right shifts
To speed up, one could use here bitwise shifts:
-
Left shift:
x << 1. The same as multiplying by 2:x * 2. -
Right shift:
x >> 1. The same as dividing by 2:x / 2.
Algorithm
Define boundaries:
-
Initiate
left = 0andright = 1. -
While target is on the right to the right boundary:
reader.get(right) < target:-
Set left boundary equal to the right one:
left = right. -
Extend right boundary:
right *= 2. To speed up, use right shift instead of multiplication:right <<= 1.
-
-
Now the target is between left and right boundaries.
Binary Search:
-
While
left <= right:-
Pick a pivot index in the middle:
pivot = (left + right) / 2. To avoid overflow, use the formpivot = left + ((right - left) >> 1)instead of straightforward expression above. -
Retrieve the element at this index:
num = reader.get(pivot). -
Compare middle element
numto the target value.-
If the middle element is the target
num == target: returnpivot. -
If the target is not yet found:
-
If
num > target, continue to search on the leftright = pivot - 1. -
Else continue to search on the right
left = pivot + 1.
-
-
-
-
We're here because target is not found. Return -1.
Implementation
Complexity Analysis
-
Time complexity : O(logT), where T is an index of target value.
There are two operations here: to define search boundaries and to perform binary search.
Let's first find the number of steps k to setup the boundaries. On the first step, the boundaries are 20..20+1, on the second step 21..21+1, etc. When everything is done, the boundaries are 2k..2k+1 and 2k<T≤2k+1. That means one needs k=logT steps to setup the boundaries, that means O(logT) time complexity.
Now let's discuss the complexity of the binary search. There are 2k+1−2k=2k elements in the boundaries, i.e. 2logT=T elements. As discussed, binary search has logarithmic complexity, that results in O(logT) time complexity.
-
Space complexity : O(1) since it's a constant space solution.
as all the elements in the array are unique there can be max 2*10^5 elements ( according to constraints ). Also if we go out of bound of array we get 2147483647 in return
So we can simply apply binary search in start=0 and end=2 *10^5
April 24, 2020 7:46 PM
We don't even need to find upper boundary in log(n) time. We can find the upper boundary in O(1) time
Explanation: Given all the elements in the Array are unique. If first value is n and we have all possible integers from n to target .
We will find the target at worst case at (target - n)
Example: If First Element is -1 and target = 5 if the array had all elements between -1 and 5 i.e.,
[-1,0,1,2,3,4,5] Worst case 5 will be at (target - firstValue)
nice article! however, left shift & right shift is wrongly represented in the definition.
I use this to find the size of the array in the worst case:
int right = Math.abs(reader.get(0)) + Math.abs(target) + 1;
Hey guys, just a reminder, If you use C#, you should use ArrayReader's API interface as reader.get(index), not reader.Get(index) in comments above.
October 23, 2020 8:26 AM
To speed up, one could use here bitwise shifts:
Interesting point. Could you provide any evidence/benchmark to back this up? Why not leave such a minute detail to the compilers (for Java, python, etc.)?
ArrayReader API interface: int get(ArrayReader *, int index); not working for C implementation. Tried using get(reader, i) and it complains:
solution.c: In function ‘search’ Line 16: Char 12: warning: implicit declaration of function ‘get’; did you mean ‘gets’? [-Wimplicit-function-declaration] while (get(reader, r)< target){ ^~~ gets solution.c: In function ‘driver_helper’ Line 49: Char 5: warning: ignoring return value of ‘freopen’, declared with attribute warn_unused_result [-Wunused-result] int r = len-1; ^~~~~~~~~~~~~~ /tmp/ccAlSpZT.o:prog_joined.c:function search: error: undefined reference to 'get' /tmp/ccAlSpZT.o:prog_joined.c:function search: error: undefined reference to 'get' /tmp/ccAlSpZT.o:prog_joined.c:function search: error: undefined reference to 'get' collect2: error: ld returned 1 exit status
May 14, 2020 9:22 PM
how about:
class Solution:
def search(self, reader: 'ArrayReader', t: int) -> int:
l, r = 0, 2 ** 31 - 1
while l <= r:
mid = l + (r - l) // 2
val = reader.get(mid)
if val == t: return mid
elif val < t: l = mid + 1
else: r = mid - 1
return -1
is it wrong to set the upper limit on the size of the array? (i.e. 2 ** 31 - 1)?
See a better approach and the explanation in my post here:
https://leetcode.com/problems/search-in-a-sorted-array-of-unknown-size/discuss/535941/Clean-binary-search-with-explanation-python-solution-no-need-doubling
No need to search for the upper bound like this here.
You don't have any submissions yet.
xxxxxxxxxx/** * // This is the ArrayReader's API interface. * // You should not implement it, or speculate about its implementation * class ArrayReader { * public: * int get(int index); * }; */class Solution {public: int search(const ArrayReader& reader, int target) { }};


